1516D - Cut - CodeForces Solution

//CP Template 3.2: Contest Mode

#include <bits/stdc++.h>

using namespace std;

#define ii pair<int, int>
#define fs first
#define sc second
#define all(v) v.begin(), v.end()
#define sz(v) ((int) v.size())
#define SUnique {sort(all(v)), v.erase(unique(all(v)), v.end());}
#define forlr(i, l, r) for (int i = l; i <= r; i++)
#define forrl(i, r, l) for (int i = r; i >= l; i--)
#define show(v) for (int i : v) cout << i << " "; cout << endl;
#define showlr(v, l, r) {forlr(i, l, r) cout << v[i] << " "; cout << endl;}
#define endl "\n"

#define int long long

const int N = 2e5 + 100;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const long long LINF = 1e16 + 100;
const int LOG = 25;

long long binPow(long long a, long long b, long long m = 1e18) {

    a %= m;
    long long res = 1;

    while (b) {

        res = (res * a) % m;
        a = (a * a) % m;
        b /= 2;

    }

    return res;

}

ostream& operator << (ostream& os, ii a) {

    os << a.fs << " " << a.sc;
    return os;

}

void setIO(string s) {

    freopen((s + ".INP").c_str(), "r", stdin);
    freopen((s + ".OUT").c_str(), "w", stdout);

}

int arr[N];
int n, q;

vector<int> pFac[N];
bool isPrime[N];

void preCompute() {

    memset(isPrime, 1, sizeof isPrime);
    isPrime[0] = isPrime[1] = 0;

    forlr(i, 2, N - 1) {

        if (isPrime[i]) {

            for (int j = i; j < N; j += i) isPrime[j] = false, pFac[j].push_back(i);

        }

    }

}

int cnt[N];
int R[N];

int up[N][LOG];

void solve() {

    cin >> n >> q;
    forlr(i, 1, n) cin >> arr[i];
    int l = 1;
    fill(R + 1, R + n + 1, n);

    int cntBad = 0;

    forlr(i, 1, n + 1) {

        for (int x : pFac[arr[i]]) {

            cnt[x]++;
            if (cnt[x] == 2) cntBad++;

        }

        while (cntBad) {

            for (int x : pFac[arr[l]]) {

                cnt[x]--;
                if (cnt[x] == 1) cntBad--;

            }

            R[l] = i - 1;
            l++;

        }

    }

    forlr(i, 0, LOG - 1) up[n + 1][i] = n;

    forrl(i, n, 1) {

        up[i][0] = R[i];
        forlr(j, 1, LOG - 1) up[i][j] = up[up[i][j - 1] + 1][j - 1];

    }
    forlr(i, 1, q) {

        int l, r; cin >> l >> r;
        int res = 0;
        forrl(level, LOG - 1, 0) {

            if (up[l][level] < r) l = up[l][level] + 1, res += (1 << level);

        }

        if (l <= r) res++;
        cout << res << endl;

    }

}

signed main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    // setIO("SOL");
    preCompute();

    bool multiTest = false;
    int T = 1;
    if (multiTest) cin >> T;

    while (T--) {

        solve();

    }

}